#include <stdio.h>
#include <stdlib.h>
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10 //分配增量
#define OK 1
#define ERROR 0
#define OVERFLOW -1

typedef int Status;
typedef int ElemType;
typedef Status(*fp)(ElemType , ElemType);

// 线性表的结构
typedef struct 
{
	// 基址
	ElemType *elem;
	int length;
	int listsize;
}SqList,List;

// 初始化线性表
Status InitList_Sq(SqList &List);
// 插入元素
Status ListInsert_Sq(SqList &L , int i, ElemType e);
// 删除线性表某个节点的元素
Status ListDelete_Sq(SqList &L,int i,ElemType e);
// 查找线性表符合compare关系的e元素，并返回对应的位置
int ListLocate_Sql(SqList L,ElemType e,fp compare);
// 获取线性表某个节点元素
void GetElem(List L,int i,ElemType &e);
// 对两个元素进行比较
Status Equal(ElemType a, ElemType b);
// 在线性表里面寻找有符合compare的e的元素
Status LocateElem(List La,ElemType e,fp compare);
// 对两个线性表进行合并
void Union(SqList &La,SqList Lb);
// 获得线性表的长度
int ListLength(SqList List);
// 把都是升序排列的La，Lb放到Lc上，仍然是升序排列
void MergeList(SqList La,SqList Lb,SqList &Lc);
// 输出线性表全部的元素
void showAllElem(SqList L);


/**
 * 两个线性表进行合并,Lb的元素在La的最后一个节点插入，在没有对应的元素前提下
 * @param La [description]
 * @param Lb [description]
 */
void Union(SqList &La,SqList Lb)
{
	ElemType e;
	int La_Length,Lb_Length;
	La_Length = ListLength(La);
	Lb_Length = ListLength(Lb);
	// 坑爹，要从1开始，因为获取节点都是从1获取
	for (int i = 1; i <= Lb_Length; ++i)
	{
		GetElem(Lb,i,e);
		if(!LocateElem(La,e,Equal))
			ListInsert_Sq(La,++La_Length,e);
	}
}

/**
 * 初始化线性表
 * @param  List [description]
 * @return      [description]
 */
Status InitList_Sq(SqList &List){
	List.elem = (ElemType*) malloc(LIST_INIT_SIZE * sizeof(ElemType));
	if(!List.elem) exit(OVERFLOW);
	List.length=0;
	List.listsize = LIST_INIT_SIZE;
	return OK;
}

int ListLength(SqList List){
	return List.length;
}
/**
 * 向线性表List的第i个元素前插入e
 * @param  List [description]
 * @param  i    [description]
 * @param  e    [description]
 * @return      [description]
 */
Status ListInsert_Sq(SqList &L , int i, ElemType e)
{
	ElemType *newbase,*p,*q;
	if(i-1>ListLength(L) || i<1) exit(ERROR);
	if(L.length >= L.listsize)
	{
		newbase = (ElemType*) realloc(L.elem,LISTINCREMENT*sizeof(ElemType));
		if(!newbase) exit(OVERFLOW);
		L.elem = newbase;
		L.listsize += LISTINCREMENT;
	}
	// 标记一下第i个元素的位置
	q = &L.elem[i-1];
	for(p=&L.elem[L.length-1];p>=q;p--)
		*(p+1) = *p;
	*q = e;
	L.length++;
	return OK;
}
/**
 * 删除L的第i个节点，并赋给e
 * @param L
 * @param i 
 * @param e
 * @return
 */

Status ListDelete_Sq(SqList &L,int i,ElemType e){
	ElemType *p,*q;
	if(i>L.length || i<1) exit(OVERFLOW);
	p = &L.elem[i-1];
	q = &L.elem[L.length-1];
	e = *q;
	for(;p<q;p++){
		*p=*(p+1);
	}
	L.length--;
	return OK;
}

int ListLocate_Sql(SqList L,ElemType e,fp compare){
	int length = ListLength(L);
	int i=1;
	ElemType *p;
	p = L.elem;
	while(i<=length && !compare(*p++,e)) 
		++i;
	if(i<=length) 
		return i;
	else 
		return 0; 
}
void MergeList_Sq(SqList La,SqList Lb,SqList &Lc){
	ElemType *pa,*pa_last,*pb,*pb_last;
	pa = La.elem;pb = Lb.elem;
	pa_last = La.elem+La.length-1;
	pb_last = Lb.elem+Lb.length-1;

	Lc.elem = (ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
	if(!Lc.elem) exit(OVERFLOW);
	ElemType *pc = Lc.elem;
	Lc.length = La.length+Lb.length;

	while(pa<=pa_last && pb<=pb_last){
		if(*pa >= *pb) *pc++ = *pb++;
		else *pc++ = *pa++;
	}
	while(pa<=pa_last) *pc++ = *pa++;
	while(pb<=pb_last) *pc++ = *pb++;
}
/**
 * 遍历线性表La找出符合e的compare关系的元素，如果没有则返回错误
 * @param  La      [description]
 * @param  e       [description]
 * @param  compare [description]
 * @return         [description]
 */
Status LocateElem(List La,ElemType e,fp compare){
	ElemType q;
	for (int i = 0; i < ListLength(La); ++i)
	{
		GetElem(La,i,q);
		if(compare(e,q))
			return OK;
	}
	return ERROR;
}


// 获取线性表里的元素
void GetElem(List L,int i,ElemType &e)
{
	e = L.elem[i-1];
}

Status Equal(ElemType a, ElemType b)
{
	if(a==b)
		return OK;
	else
		return ERROR;
}
/**
 * 把都是升序排列的La，Lb放到Lc上，Lc仍然是升序排列
 * @param La [description]
 * @param Lb [description]
 * @param Lc [description]
 */
void MergeList(SqList La,SqList Lb,SqList &Lc)
{
	int La_Length = ListLength(La);
	int Lb_Length = ListLength(Lb);
	int i,j,k;
	i=j=1;k=0;
	ElemType e1,e2;
	InitList_Sq(Lc);
	// 对两组线性表进行比较，并选取晓得赋值给Lc
	while(i<=La_Length && j<=Lb_Length)
	{
		GetElem(La,i,e1);
		GetElem(Lb,j,e2);
		if(e1<e2){ ListInsert_Sq(Lc,++k,e1); i++; }
		else{ ListInsert_Sq(Lc,++k,e2); j++; }
	}
	// 处理还没赋值完的线性表
	for (; i <= La_Length; ++i)
	{
		GetElem(La,i,e1);
		ListInsert_Sq(Lc,++k,e1);
	}
	for (; j <= Lb_Length; ++j)
	{
		GetElem(Lb,j,e2);
		ListInsert_Sq(Lc,++k,e2);
	}
	Lc.length = La_Length+ Lb_Length;
}

void showAllElem(SqList L){
	int length = L.length;
	for (int i = 0; i < length; ++i)
	{

		printf("%d\n", L.elem[i]);
	}
}